//637 Average of Levels in Binary Tree
/*
给定一个二叉树，求每一层的节点值的平均数

输入是一个二叉树，输出是一个一维数组，表示每层节点值的平均数

Input:
		3
	   / \
	  9  20
		 / \
		15  7
Output: [3, 14.5, 11]



*/
vector<double> averageOfLevels(TreeNode *root)
{
	vector<double> ans;
	if (!root)
	{
		return ans;
	}
	queue<TreeNode *> q;
	q.push(root);
	while (!q.empty())
	{
		int count = q.size();
		double sum = 0;
		for (int i = 0; i < count; ++i)
		{
			TreeNode *node = q.front();
			q.pop();
			sum += node->val;
			if (node->left)
			{
				q.push(node->left);
			}
			if (node->right)
			{
				q.push(node->right);
			}
		}
		ans.push_back(sum / count);
	}
	return ans;
}